/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 19:38:33 2020
 * 
 * @brief  Dijkstra
 * 
 * 
 */

#include <iostream>
#define BLACK 2
#define GRAY 1
#define WHITE 0

template <typename T>
class Graph {
private:
    typedef int Color;
    class Node {
    public:
	T data;
	Node * next;
	int index; //mark the position
	int power; //the power of each edge
	int distance; //evaluate the distance to s
	Color color; //mark the condition
    };
    int max;
    int num;    
    int * matrix;
    Node ** adj_list; //the adjacency list
    Node ** BST(T _x);
    void relax(Node * _u, Node ** _result);
    Node * catch_min(); //get the minimun gray node
public:
    Graph(int n);
    void start_BST(T _x);
    void insert(); //get the graph data and insert the list and matrix
    void matrix_init(); //insert the matrix
    void print(); //print the list and the matrix
    ~Graph();
};

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 31 10:55:51 2020
 * 
 * @brief  get the minimun distance node
 * 
 * 
 */

template <typename T>
typename Graph<T>::Node * Graph<T>::catch_min() {
    Node * min = NULL;
    for (int i=0;i<num;i++) {
	//search the minimun gray node
	if (adj_list[i]->color==GRAY) {
	    if (min==NULL || (adj_list[i]->distance)<(min->distance)) {
	        min = adj_list[i];
	    }
	}
    }
    return min;
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 31 09:59:55 2020
 * 
 * @brief  relax
 * if _u -> _v, compare d(_u, _v) + d(s, _u) with d(s, _v)  
 * 
 */

template <typename T>
void Graph<T>::relax(Node * _u, Node ** _result) {
    //if _u->_v, relax
    Node * p = _u->next;
    while (p!=NULL) {
	int index = p->index;
	if (adj_list[index]->color==GRAY) {
	    if ((_u->distance+p->power)<adj_list[index]->distance) {
		adj_list[index]->distance = _u->distance + p->power;
		_result[index]->next = _result[_u->index];
	    }
	}
	p = p->next;
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Wed Dec 30 19:12:11 2020
 * 
 * @brief  BST function
 * 
 * 
 */

template <typename T>
void Graph<T>::start_BST(T _x) {
    Node ** result = BST(_x);
    //this function print the result of BST
    std::cout << std::endl;
    std::cout << "The distance to " << _x << ":" << std::endl;
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " distance = " << adj_list[i]->distance << ", path: ";
	Node * p = result[i];
	while (p->next!=NULL) {
	    std::cout << p->data << "->";
	    p = p->next;
	}
	std::cout << p->data;
	std::cout << std::endl;
    }
    delete [] result;
}

template <typename T>
typename Graph<T>::Node ** Graph<T>::BST(T _x) {
    //result record the connection of each node
    Node ** result = new Node* [num];
    Node * min;
    //find the _x
    for (int i=0;i<num;i++) {
	if (adj_list[i]->data==_x) {
	    min = adj_list[i];
	    min->distance = 0;
	    min->color = GRAY;
	    break;
	}
    }
    //init result
    for (int i=0;i<num;i++) {
	result[i] = new Node;
	result[i]->data = adj_list[i]->data;
	result[i]->next = NULL;
    }
    //loop for NUM times
    for (int i=0;i<num;i++) {
	//relax min and its adjacent node, then mark it Black
	relax(min, result);
	min->color = BLACK;
	Node * p = min->next;
	//change the adjacent node to Gray, and caculate the distance
	while (p!=NULL) {
	    int index = p->index;
	    if (adj_list[index]->color==WHITE) {
	        adj_list[index]->color = GRAY;
		result[index]->next = result[min->index];
		adj_list[index]->distance = p->power + min->distance;
	    }
	    p = p->next;
	}
	//find the new mininum node
	Node * q = catch_min();
	if (q!=NULL) {
	    min = q;
	}
    }
    return result;
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:08:29 2020
 * 
 * @brief  init function
 * 
 * 
 */

template <typename T>
Graph<T>::Graph(int n) {
    max = 0;
    num = n;
    matrix = new int [n*n];
    adj_list = new Node* [n];
    //init the matrix
    for (int i=0;i<n*n;i++) {
	matrix[i] = 0;
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:08:53 2020
 * 
 * @brief  init the matrix
 * 
 * 
 */

template <typename T>
void Graph<T>::matrix_init() {
    //storage the node
    T node[num];
    for (int i=0;i<num;i++) {
	node[i] = adj_list[i]->data;
    }
    for (int i=0;i<num;i++) {
	for (int j=0;j<num;j++) {
	    Node * p = adj_list[i]->next;
	    while (p!=NULL) {
		for (int k=0;k<num;k++) {
		    if (p->data==node[k]) {
			matrix[i*num+k] = 1;
			break;
		    }
		}
		p = p->next;
	    }
	}
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:10:24 2020
 * 
 * @brief  insert function
 * 
 * 
 */

template <typename T>
void Graph<T>::insert() {
    max++;
    //get the data
    T _data[num];
    int _n[num];
    T _link[num*num];
    int _d[num*num];
    int index = 0;
    for (int i=0;i<num;i++) {
	std::cin >> _data[i];
	std::cin >> _n[i];
	for (int j=0;j<_n[i];j++) {
	    std::cin >> _link[index];
	    std::cin >> _d[index];
	    if (_d[index]>0) {
		max += _d[index];
	    }
	    index++;
	}
    }

    //set the list
    index = 0;
    for (int i=0;i<num;i++) {
	adj_list[i] = new Node;
	adj_list[i]->data = _data[i];
	adj_list[i]->index = i;
	adj_list[i]->power = 0;
	adj_list[i]->distance = max;
	adj_list[i]->color = WHITE;
	adj_list[i]->next = NULL;
	Node * p = adj_list[i];
	for (int j=0;j<_n[i];j++) {
	    p->next = new Node;
	    p = p->next;
	    p->distance = max;
	    p->power = _d[index];
	    p->data = _link[index];
	    for (int k=0;k<num;k++) {
		if (p->data==_data[k]) {
		    p->index = k;
		    break;
		}
	    }
	    p->next = NULL;
	    index++;
	}
    }
    matrix_init();
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:18:51 2020
 * 
 * @brief  init the matrix
 * 
 * 
 */

template <typename T>
void Graph<T>::print() {
    std::cout << "Adjacency list:" << std::endl;
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " " << adj_list[i]->index;
	Node * p = adj_list[i]->next;
	while (p!=NULL) {
	    std::cout  << "->" << p->data << " " << p->power;
	    p = p->next;
	}
	std::cout << std::endl;
    }
    std::cout << std::endl;
    std::cout << "Adjacency matrix:" << std::endl;
    std::cout << "  "; 
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " ";
    }
    std::cout << std::endl;
    for (int i=0;i<num;i++) {
	std::cout << adj_list[i]->data << " ";
	for (int j=0;j<num;j++) {
	    std::cout << matrix[i*num+j] << " ";
	}
	std::cout << std::endl;
    }
}

/**
 * @file   Graph.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Dec 24 23:18:39 2020
 * 
 * @brief  delete the list and the matrix
 * 
 * 
 */

template <typename T>
Graph<T>::~Graph() {
    for (int i=0;i<num;i++) {
	Node * p = adj_list[i]->next;
	Node * last = p;
	while (p!=NULL) {
	    last = p;
	    p = p->next;
	    delete last;
	}
	delete adj_list[i];
    }
    delete [] matrix;
    delete [] adj_list;
}
